/*
 * @lc app=leetcode.cn id=76 lang=cpp
 * @lcpr version=30204
 *
 * [76] 最小覆盖子串
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    string minWindow(string s, string t)
    {
        char count[128] = {};
        int less = 0; // t中字符的种类
        for (auto e : t)
        {
            if (count[e] == 0)
            {
                less++;
            }
            count[e]++;
        }
        // 滑动窗口
        int ans_left = -1, ans_right = s.size();
        int left = 0;
        for (int right = 0; right < s.size(); ++right)
        {
            char ch = s[right];
            count[ch]--;
            if (count[ch] == 0)
            {
                less--;
            }
            // 字符种类为0，说明s中包含了t的字符
            while (less == 0)
            {
                if (right - left < ans_right - ans_left)
                {
                    ans_left = left;
                    ans_right = right;
                }
                char x = s[left];
                if (count[x] == 0)
                {
                    less++;
                }
                count[x]++;
                left++;
            }
        }
        return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 1);
    }
};
// @lc code=end

/*
// @lcpr case=start
// "ADOBECODEBANC"\n"ABC"\n
// @lcpr case=end

// @lcpr case=start
// "a"\n"a"\n
// @lcpr case=end

// @lcpr case=start
// "a"\n"aa"\n
// @lcpr case=end

 */
